import java.util.HashSet;
import java.util.List;

class Solution648 {
    public String replaceWords(List<String> dictionary, String sentence) {
        StringBuilder strbu = new StringBuilder();
        HashSet<String> set = new HashSet<>() ;
        String[] arr = sentence.split(" ") ; 
         for(String str : dictionary){
            set.add(str) ; 
         }
        for(int j=0 ; j < arr.length ; j ++){
            String str = arr[j] ; 
             String ret = null ; 
           for(int i=0 ; i < str.length() ; i ++){
               ret = str.substring(0,i+1) ; 
              if(set.contains(ret)){
                break ;
              } 
           }
           strbu.append(ret) ; 
           if(j != arr.length-1)
           strbu.append(" ");
        }
   
       return strbu.toString() ;
    }
}